public class 砍竹子II {

    public static int mod = 1000000007;
    public int cuttingBamboo(int n) {
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        int x = n % 3; // 模 3 的值
        int y = x == 0 ? n / 3 : x == 1 ? n / 3 - 1 : n / 3; // 3 的数量
        int tail = x == 0 ? 1 : x == 1 ? 4 : 2;
        return (int)(tail * power(3,y) % mod);
    }

    private long power(long x, int n) {
        long ans = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                ans = (ans * x) % mod;
            }
            n >>= 1;
            x = (x * x) % mod;
        }
        return ans;
    }
}
